home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / nobtree / nobtutils.c < prev   
Encoding:
C/C++ Source or Header  |  1992-08-27  |  13.3 KB  |  535 lines
  1. /*
  2.  *  btutils.c -- Utility code for Postgres btree implementation.
  3.  */
  4.  
  5. #include "tmp/c.h"
  6.  
  7. #ifdef NOBTREE
  8. #include "tmp/postgres.h"
  9.  
  10. #include "storage/bufmgr.h"
  11. #include "storage/bufpage.h"
  12. #include "storage/page.h"
  13.  
  14. #include "utils/log.h"
  15. #include "utils/rel.h"
  16. #include "utils/excid.h"
  17.  
  18. #include "access/heapam.h"
  19. #include "access/genam.h"
  20. #include "access/iqual.h"
  21. #include "access/ftup.h"
  22. #include "access/tupmacs.h"
  23. #include "access/nobtree.h"
  24.  
  25. RcsId("$Header: /private/postgres/src/access/nobtree/RCS/nobtutils.c,v 1.7 1991/06/26 19:12:14 mao Exp $");
  26.  
  27. ScanKey
  28. _nobt_mkscankey(rel, itup)
  29.     Relation rel;
  30.     IndexTuple itup;
  31. {
  32.     ScanKey skey;
  33.     TupleDescriptor itupdesc;
  34.     int natts;
  35.     int i;
  36.     Pointer arg;
  37.     RegProcedure proc;
  38.     Boolean null;
  39.  
  40.     natts = rel->rd_rel->relnatts;
  41.     itupdesc = RelationGetTupleDescriptor(rel);
  42.  
  43.     skey = (ScanKey) palloc(natts * sizeof(ScanKeyEntryData));
  44.  
  45.     for (i = 0; i < natts; i++) {
  46.     arg = (Pointer) index_getattr(itup, i + 1, itupdesc, &null);
  47.     proc = index_getprocid(rel, i + 1, NOBTORDER_PROC);
  48.     ScanKeyEntryInitialize(&(skey->data[i]), 0x0, i + 1, proc, arg);
  49.     }
  50.  
  51.     return (skey);
  52. }
  53.  
  54. ScanKey
  55. _nobt_imkscankey(rel, iitem)
  56.     Relation rel;
  57.     NOBTIItem iitem;
  58. {
  59.     ScanKey skey;
  60.     TupleDescriptor itupdesc;
  61.     int natts;
  62.     int i;
  63.     Pointer arg;
  64.     RegProcedure proc;
  65.     char *tempd;
  66.  
  67.     natts = rel->rd_rel->relnatts;
  68.     itupdesc = RelationGetTupleDescriptor(rel);
  69.     tempd = ((char *) iitem) + sizeof(NOBTIItemData);
  70.  
  71.     skey = (ScanKey) palloc(natts * sizeof(ScanKeyEntryData));
  72.  
  73.     for (i = 0; i < natts; i++) {
  74.     arg = (Pointer) fetchatt(((struct attribute **) itupdesc), tempd);
  75.     proc = index_getprocid(rel, i + 1, NOBTORDER_PROC);
  76.     ScanKeyEntryInitialize(&(skey->data[i]), 0x0, i + 1, proc, arg);
  77.     }
  78.  
  79.     return (skey);
  80. }
  81.  
  82. void
  83. _nobt_freeskey(skey)
  84.     ScanKey skey;
  85. {
  86.     pfree (skey);
  87. }
  88.  
  89. void
  90. _nobt_freestack(stack)
  91.     NOBTStack stack;
  92. {
  93.     NOBTStack ostack;
  94.  
  95.     while (stack != (NOBTStack) NULL) {
  96.     ostack = stack;
  97.     stack = stack->nobts_parent;
  98.     pfree(ostack->nobts_btitem);
  99. #ifndef    NORMAL
  100.     if (ostack->nobts_nxtitem != (NOBTIItem) NULL)
  101.         pfree(ostack->nobts_nxtitem);
  102. #endif    /* ndef NORMAL */
  103.     pfree(ostack);
  104.     }
  105. }
  106.  
  107. void
  108. _nobt_orderkeys(relation, numberOfKeys, key)
  109.     Relation relation;
  110.     uint16 *numberOfKeys;
  111.     ScanKey key;
  112. {
  113.     ScanKey xform;
  114.     ScanKeyEntryData *cur;
  115.     StrategyMap map;
  116.     int nbytes;
  117.     int test;
  118.     int i, j;
  119.     int init[NOBTMaxStrategyNumber];
  120.  
  121.     /* haven't looked at any strategies yet */
  122.     for (i = 0; i <= NOBTMaxStrategyNumber; i++)
  123.     init[i] = 0;
  124.  
  125.     /* get space for the modified array of keys */
  126.     nbytes = NOBTMaxStrategyNumber * sizeof (ScanKeyEntryData);
  127.     xform = (ScanKey) palloc(nbytes);
  128.     bzero(xform, nbytes);
  129.  
  130.     /* get the strategy map for this index/attribute pair */
  131.     /*
  132.      *  XXX
  133.      *  When we support multiple keys in a single index, this is what
  134.      *  we'll want to do.  At present, the planner is hosed, so we
  135.      *  hard-wire the attribute number below.  Postgres only does single-
  136.      *  key indices...
  137.      * map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation),
  138.      *                     NOBTMaxStrategyNumber,
  139.      *                     key->data[0].attributeNumber);
  140.      */
  141.      map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation),
  142.                     NOBTMaxStrategyNumber,
  143.                     1 /* XXX */ );
  144.  
  145.     /* check each key passed in */
  146.     for (i = *numberOfKeys; --i >= 0; ) {
  147.     cur = &(key->data[i]);
  148.     for (j = NOBTMaxStrategyNumber; --j >= 0; ) {
  149.         if (cur->procedure == map->entry[j].procedure)
  150.             break;
  151.     }
  152.  
  153.     /* have we seen one of these before? */
  154.     if (init[j]) {
  155.         /* yup, use the appropriate value */
  156.         test = (int) (*(cur->func))(cur->argument,
  157.                         xform->data[j].argument);
  158.         if (test)
  159.         xform->data[j].argument = cur->argument;
  160.     } else {
  161.         /* nope, use this value */
  162.         bcopy(cur, &xform->data[j], sizeof (*cur));
  163.         init[j] = 1;
  164.     }
  165.     }
  166.  
  167.     /* if = has been specified, no other key will be used */
  168.     if (init[NOBTEqualStrategyNumber - 1]) {
  169.     init[NOBTLessStrategyNumber - 1] = 0;
  170.     init[NOBTLessEqualStrategyNumber - 1] = 0;
  171.     init[NOBTGreaterEqualStrategyNumber - 1] = 0;
  172.     init[NOBTGreaterStrategyNumber - 1] = 0;
  173.     }
  174.  
  175.     /* only one of <, <= */
  176.     if (init[NOBTLessStrategyNumber - 1]
  177.     && init[NOBTLessEqualStrategyNumber - 1]) {
  178.  
  179.     ScanKeyEntryData *lt, *le;
  180.  
  181.     lt = &xform->data[NOBTLessStrategyNumber - 1];
  182.     le = &xform->data[NOBTLessEqualStrategyNumber - 1];
  183.  
  184.     /*
  185.      *  DO NOT use the cached function stuff here -- this is key
  186.      *  ordering, happens only when the user expresses a hokey
  187.      *  qualification, and gets executed only once, anyway.  The
  188.      *  transform maps are hard-coded, and can't be initialized
  189.      *  in the correct way.
  190.      */
  191.  
  192.     test = (int) fmgr(le->procedure, le->argument, lt->argument);
  193.  
  194.     if (test)
  195.         init[NOBTLessEqualStrategyNumber - 1] = 0;
  196.     else
  197.         init[NOBTLessStrategyNumber - 1] = 0;
  198.     }
  199.  
  200.     /* only one of >, >= */
  201.     if (init[NOBTGreaterStrategyNumber - 1]
  202.     && init[NOBTGreaterEqualStrategyNumber - 1]) {
  203.  
  204.     ScanKeyEntryData *gt, *ge;
  205.  
  206.     gt = &xform->data[NOBTGreaterStrategyNumber - 1];
  207.     ge = &xform->data[NOBTGreaterEqualStrategyNumber - 1];
  208.  
  209.     /* see note above on function cache */
  210.     test = (int) fmgr(ge->procedure, gt->argument, gt->argument);
  211.  
  212.     if (test)
  213.         init[NOBTGreaterStrategyNumber - 1] = 0;
  214.     else
  215.         init[NOBTGreaterEqualStrategyNumber - 1] = 0;
  216.     }
  217.  
  218.     /* okay, reorder and count */
  219.     j = 0;
  220.  
  221.     for (i = NOBTMaxStrategyNumber; --i >= 0; )
  222.     if (init[i])
  223.         key->data[j++] = xform->data[i];
  224.  
  225.     *numberOfKeys = j;
  226.  
  227.     pfree (xform);
  228. }
  229.  
  230. #include <stdio.h>
  231.  
  232. _nobt_dump(rel)
  233.     Relation rel;
  234. {
  235.     Buffer buf;
  236.     Page page;
  237.     NOBTPageOpaque opaque;
  238.     ItemId itemid;
  239.     OffsetIndex offind, maxoff, start;
  240.     BlockNumber nxtbuf;
  241.     TupleDescriptor itupdesc;
  242.     Boolean isnull;
  243.     Datum keyvalue;
  244.     uint16 flags;
  245.     BlockNumber i, nblocks;
  246.  
  247.     printf("----------------------- tree dump --------------------------\n");
  248.     nblocks = RelationGetNumberOfBlocks(rel);
  249.     itupdesc = RelationGetTupleDescriptor(rel);
  250.  
  251.     for (i = 1; i < nblocks; i++) {
  252.     buf = _nobt_getbuf(rel, i, NOBT_READ);
  253.     page = BufferGetPage(buf, 0);
  254.     opaque = (NOBTPageOpaque) PageGetSpecialPointer(page);
  255.  
  256.     printf("page %d prev %d next %d", BufferGetBlockNumber(buf),
  257.         opaque->nobtpo_prev, opaque->nobtpo_next);
  258.  
  259.     flags = opaque->nobtpo_flags;
  260.  
  261.     if (flags & NOBTP_ROOT)
  262.         printf (" <root>");
  263.     if (flags & NOBTP_LEAF)
  264.         printf (" <leaf>");
  265.     if (flags & NOBTP_FREE)
  266.         printf (" <free>");
  267.  
  268.     printf("\n");
  269.  
  270.     if (opaque->nobtpo_next != P_NONE) {
  271.         printf("    high key:");
  272.         _nobt_dumptup(rel, itupdesc, page, 0);
  273.         start = 1;
  274.     } else {
  275.         printf(" no high key\n");
  276.         start = 0;
  277.     }
  278.  
  279.     maxoff = PageGetMaxOffsetIndex(page);
  280.     if (!PageIsEmpty(page) &&
  281.          (opaque->nobtpo_next == P_NONE || maxoff != start)) {
  282.         for (offind = start; offind <= maxoff; offind++) {
  283.         printf("\t{%d} ", offind + 1);
  284.         _nobt_dumptup(rel, itupdesc, page, offind);
  285.         }
  286.     }
  287.     _nobt_relbuf(rel, buf, NOBT_READ);
  288.     }
  289. }
  290.  
  291. #include "tmp/datum.h"
  292.  
  293. _nobt_dumptup(rel, itupdesc, page, offind)
  294.     Relation rel;
  295.     TupleDescriptor itupdesc;
  296.     Page page;
  297.     OffsetIndex offind;
  298. {
  299.     ItemId itemid;
  300.     Size itemsz;
  301.     NOBTIItem btiitem;
  302.     NOBTLItem btlitem;
  303.     IndexTuple itup;
  304.     Size tuplen;
  305.     ItemPointer iptr;
  306.     BlockNumber blkno;
  307.     BlockNumber oldblkno;
  308.     PageNumber pgno;
  309.     OffsetNumber offno;
  310.     Datum idatum;
  311.     int16 tmpkey;
  312.     Boolean null;
  313.     bool isleaf;
  314.     NOBTPageOpaque opaque;
  315.     char *tempd;
  316.  
  317.     opaque = (NOBTPageOpaque) PageGetSpecialPointer(page);
  318.  
  319.     if (opaque->nobtpo_flags & NOBTP_LEAF)
  320.     isleaf = true;
  321.     else
  322.     isleaf = false;
  323.  
  324.     itemid = PageGetItemId(page, offind);
  325.     itemsz = ItemIdGetLength(itemid);
  326.     if (isleaf) {
  327.     btlitem = (NOBTLItem) PageGetItem(page, itemid);
  328.     itup = &(btlitem->nobtli_itup);
  329.     tuplen = IndexTupleSize(itup);
  330.     iptr = &(itup->t_tid);
  331.     blkno = ItemPointerGetBlockNumber(iptr);
  332.     pgno = ItemPointerGetPageNumber(iptr, 0);
  333.     offno = ItemPointerGetOffsetNumber(iptr, 0);
  334.  
  335.     idatum = IndexTupleGetAttributeValue(itup, 1, itupdesc, &null);
  336.     tmpkey = DatumGetInt16(idatum);
  337.  
  338.     printf("[%d/%d bytes] <%d,%d,%d> %d\n", itemsz, tuplen,
  339.         blkno, pgno, offno, tmpkey);
  340.     } else {
  341.     btiitem = (NOBTIItem) PageGetItem(page, itemid);
  342.     tempd = ((char *) btiitem) + sizeof(NOBTIItemData);
  343.     blkno = btiitem->nobtii_child;
  344. #ifdef    SHADOW
  345.     oldblkno = btiitem->nobtii_oldchild;
  346. #endif    /* SHADOW */
  347.     tuplen = NOBTIItemGetSize(btiitem);
  348.  
  349.     idatum = (Datum) fetchatt(((struct attribute **) itupdesc), tempd);
  350.     tmpkey = DatumGetInt16(idatum);
  351.  
  352. #ifdef    SHADOW
  353.     printf("[%d/%d bytes] child %d [%d] %d\n", itemsz, tuplen,
  354.         blkno, oldblkno, tmpkey);
  355. #else    /* SHADOW */
  356.     printf("[%d/%d bytes] child %d %d\n", itemsz, tuplen, blkno, tmpkey);
  357. #endif    /* SHADOW */
  358.     }
  359. }
  360.  
  361. bool
  362. _nobt_checkqual(scan, itup)
  363.     IndexScanDesc scan;
  364.     IndexTuple itup;
  365. {
  366.     if (scan->numberOfKeys > 0)
  367.     return (ikeytest(itup, scan->relation,
  368.              scan->numberOfKeys, &(scan->keyData)));
  369.     else
  370.     return (true);
  371. }
  372.  
  373. NOBTLItem
  374. _nobt_formitem(itup)
  375.     IndexTuple itup;
  376. {
  377.     int nbytes_btitem;
  378.     NOBTLItem btitem;
  379.     Size tuplen = IndexTupleSize(itup);
  380.  
  381.     /* make a copy of the index tuple with room for the sequence number */
  382.     nbytes_btitem = tuplen +
  383.             (sizeof(NOBTLItemData) - sizeof(IndexTupleData));
  384.  
  385.     btitem = (NOBTLItem) palloc(nbytes_btitem);
  386.     bcopy((char *) itup, (char *) &(btitem->nobtli_itup), tuplen);
  387.  
  388.     return (btitem);
  389. }
  390.  
  391. NOBTIItem
  392. _nobt_formiitem(bkno, datump, dsize)
  393.     BlockNumber bkno;
  394.     char *datump;
  395.     Size dsize;
  396. {
  397.     int nbytes_btitem;
  398.     NOBTIItem btitem;
  399.     char *tempd;
  400.  
  401.     /* make a copy of the index tuple with room for the sequence number */
  402.     nbytes_btitem = dsize + sizeof(NOBTIItemData);
  403.     nbytes_btitem = LONGALIGN(nbytes_btitem);
  404.  
  405.     btitem = (NOBTIItem) palloc(nbytes_btitem);
  406.     btitem->nobtii_child = bkno;
  407. #ifdef    SHADOW
  408.     btitem->nobtii_oldchild = P_NONE;
  409.     btitem->nobtii_filler = 0;
  410. #endif    /* SHADOW */
  411.     btitem->nobtii_info = nbytes_btitem;
  412.  
  413.     tempd = ((char *) btitem) + sizeof(NOBTIItemData);
  414.     bcopy(datump, tempd, dsize);
  415.  
  416.     return (btitem);
  417. }
  418.  
  419. struct timeval {
  420.     long    tv_sec;
  421.     long    tv_usec;
  422. };
  423.  
  424. struct timezone {
  425.     int        tz_minuteswest;
  426.     int        tz_dsttime;
  427. };
  428.  
  429. #include <sys/resource.h>
  430.  
  431. struct rusage _base_r;
  432. struct timeval _base_t;
  433. struct rusage _count_r;
  434. struct timeval _count_t;
  435. int NOBT_NSplits = 0;
  436.  
  437. _nobt_countstart()
  438. {
  439.     struct timezone tz;
  440.  
  441.     getrusage(RUSAGE_SELF, &_base_r);
  442.     gettimeofday(&_base_t, &tz);
  443. }
  444.  
  445. _nobt_countstop()
  446. {
  447.     struct rusage r;
  448.     struct timeval elapsed;
  449.     struct timezone tz;
  450.  
  451.     getrusage(RUSAGE_SELF, &r);
  452.     gettimeofday(&elapsed, &tz);
  453.  
  454.     if (elapsed.tv_usec < _base_t.tv_usec) {
  455.     elapsed.tv_sec--;
  456.     elapsed.tv_usec += 1000000;
  457.     }
  458.     if (r.ru_utime.tv_usec < _base_r.ru_utime.tv_usec) {
  459.     r.ru_utime.tv_sec--;
  460.     r.ru_utime.tv_usec += 1000000;
  461.     }
  462.     if (r.ru_stime.tv_usec < _base_r.ru_stime.tv_usec) {
  463.     r.ru_stime.tv_sec--;
  464.     r.ru_stime.tv_usec += 1000000;
  465.     }
  466.  
  467.     _count_r.ru_utime.tv_sec += (r.ru_utime.tv_sec - _base_r.ru_utime.tv_sec);
  468.     _count_r.ru_utime.tv_usec += (r.ru_utime.tv_usec
  469.                    - _base_r.ru_utime.tv_usec);
  470.     _count_r.ru_stime.tv_sec += (r.ru_stime.tv_sec - _base_r.ru_stime.tv_sec);
  471.     _count_r.ru_stime.tv_usec += (r.ru_stime.tv_usec
  472.                    - _base_r.ru_stime.tv_usec);
  473.     _count_t.tv_sec += (elapsed.tv_sec - _base_t.tv_sec);
  474.     _count_t.tv_usec += (elapsed.tv_usec - _base_t.tv_usec);
  475.  
  476.     if (_count_t.tv_usec >= 1000000) {
  477.     _count_t.tv_sec += (_count_t.tv_usec / 1000000);
  478.     _count_t.tv_usec %= 1000000;
  479.     }
  480.  
  481.     if (_count_r.ru_utime.tv_usec >= 1000000) {
  482.     _count_r.ru_utime.tv_sec += (_count_r.ru_utime.tv_usec / 1000000);
  483.     _count_r.ru_utime.tv_usec %= 1000000;
  484.     }
  485.  
  486.     if (_count_r.ru_stime.tv_usec >= 1000000) {
  487.     _count_r.ru_stime.tv_sec += (_count_r.ru_stime.tv_usec / 1000000);
  488.     _count_r.ru_stime.tv_usec %= 1000000;
  489.     }
  490.  
  491.     _count_r.ru_inblock += (r.ru_inblock - _base_r.ru_inblock);
  492.     _count_r.ru_oublock += (r.ru_oublock - _base_r.ru_oublock);
  493.     _count_r.ru_majflt += (r.ru_majflt - _base_r.ru_majflt);
  494.     _count_r.ru_minflt += (r.ru_minflt - _base_r.ru_minflt);
  495.     _count_r.ru_nswap += (r.ru_nswap - _base_r.ru_nswap);
  496.     _count_r.ru_nsignals += (r.ru_nsignals - _base_r.ru_nsignals);
  497.     _count_r.ru_msgrcv += (r.ru_msgrcv - _base_r.ru_msgrcv);
  498.     _count_r.ru_msgsnd += (r.ru_msgsnd - _base_r.ru_msgsnd);
  499.     _count_r.ru_nvcsw += (r.ru_nvcsw - _base_r.ru_nvcsw);
  500.     _count_r.ru_nivcsw += (r.ru_nivcsw - _base_r.ru_nivcsw);
  501. }
  502.  
  503. _nobt_countinit()
  504. {
  505.     bzero(&_count_r, sizeof(_count_r));
  506.     bzero(&_count_t, sizeof(_count_t));
  507.     NOBT_NSplits = 0;
  508. }
  509.  
  510. #include <stdio.h>
  511.  
  512. _nobt_countout()
  513. {
  514.     fprintf(stderr,
  515.         "!\t%ld.%06ld elapse %ld.%06ld user %ld.%06ld system sec\n",
  516.         _count_t.tv_sec, _count_t.tv_usec,
  517.         _count_r.ru_utime.tv_sec, _count_r.ru_utime.tv_usec,
  518.         _count_r.ru_stime.tv_sec, _count_r.ru_stime.tv_usec);
  519.     fprintf(stderr,
  520.         "!\t%d/%d fs blocks in/out\n",
  521.         _count_r.ru_inblock, _count_r.ru_oublock);
  522.     fprintf(stderr,
  523.         "!\t%d/%d page faults/reclaims, %d swaps\n",
  524.         _count_r.ru_majflt, _count_r.ru_minflt, _count_r.ru_nswap);
  525.     fprintf(stderr,
  526.         "!\t%d signals received, %d/%d messages received/sent\n",
  527.         _count_r.ru_nsignals, _count_r.ru_msgrcv, _count_r.ru_msgsnd);
  528.     fprintf(stderr,
  529.         "!\t%d/%d voluntary/involuntary context switches\n",
  530.         _count_r.ru_nvcsw, _count_r.ru_nivcsw);
  531.     fprintf(stderr, "!\t%d page splits\n", NOBT_NSplits);
  532. }
  533.  
  534. #endif /* NOBTREE */
  535.